#include <iostream>
#include <vector>
#include <algorithm>

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
};

class Solution 
{
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode * fast = head;
        ListNode * slow = head;
        bool flag = false;
        while (fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow)
            {
                flag = true;
                break;
            }
        }
        if(flag)
        {
            slow = head;
            while (slow != fast)
            {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
        else
        {
            return nullptr;
        }
    }
};

// 辅助函数：根据数组创建链表（不带环）
ListNode* createList(const std::vector<int>& vals) {
    if (vals.empty()) return nullptr;
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    for (int v : vals) {
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

// 辅助函数：根据数组创建带环链表，pos为环的入口下标（0-based），-1表示无环
ListNode* createCycleList(const std::vector<int>& vals, int pos) {
    if (vals.empty()) return nullptr;
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    ListNode* cycleEntry = nullptr;
    for (int i = 0; i < vals.size(); ++i) {
        cur->next = new ListNode(vals[i]);
        cur = cur->next;
        if (i == pos) {
            cycleEntry = cur;
        }
    }
    if (pos != -1) {
        cur->next = cycleEntry;
    }
    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

// 辅助函数：打印链表（只打印前n个节点，防止死循环）
void printList(ListNode* head, int n = 20) {
    ListNode* cur = head;
    int cnt = 0;
    while (cur && cnt < n) {
        std::cout << cur->val;
        if (cur->next && cnt < n - 1) std::cout << "->";
        cur = cur->next;
        ++cnt;
    }
    if (cur) std::cout << "->...";
    std::cout << std::endl;
}

int main() {
    Solution sol;

    // 测试用例1：有环，环入口在索引1（值为2）
    std::vector<int> vals1 = {3, 2, 0, -4};
    int pos1 = 1;
    ListNode* head1 = createCycleList(vals1, pos1);
    std::cout << "测试用例1：有环，环入口值应为2" << std::endl;
    ListNode* entry1 = sol.detectCycle(head1);
    if (entry1) {
        std::cout << "环入口节点值: " << entry1->val << std::endl;
    } else {
        std::cout << "无环" << std::endl;
    }
    std::cout << std::endl;

    // 测试用例2：有环，环入口在索引0（值为1）
    std::vector<int> vals2 = {1, 2};
    int pos2 = 0;
    ListNode* head2 = createCycleList(vals2, pos2);
    std::cout << "测试用例2：有环，环入口值应为1" << std::endl;
    ListNode* entry2 = sol.detectCycle(head2);
    if (entry2) {
        std::cout << "环入口节点值: " << entry2->val << std::endl;
    } else {
        std::cout << "无环" << std::endl;
    }
    std::cout << std::endl;

    // 测试用例3：无环
    std::vector<int> vals3 = {1};
    int pos3 = -1;
    ListNode* head3 = createCycleList(vals3, pos3);
    std::cout << "测试用例3：无环" << std::endl;
    ListNode* entry3 = sol.detectCycle(head3);
    if (entry3) {
        std::cout << "环入口节点值: " << entry3->val << std::endl;
    } else {
        std::cout << "无环" << std::endl;
    }
    std::cout << std::endl;

    // 测试用例4：空链表
    ListNode* head4 = nullptr;
    std::cout << "测试用例4：空链表" << std::endl;
    ListNode* entry4 = sol.detectCycle(head4);
    if (entry4) {
        std::cout << "环入口节点值: " << entry4->val << std::endl;
    } else {
        std::cout << "无环" << std::endl;
    }
    std::cout << std::endl;

    // 测试用例5：有环，环入口在索引2（值为3）
    std::vector<int> vals5 = {1, 2, 3, 4, 5};
    int pos5 = 2;
    ListNode* head5 = createCycleList(vals5, pos5);
    std::cout << "测试用例5：有环，环入口值应为3" << std::endl;
    ListNode* entry5 = sol.detectCycle(head5);
    if (entry5) {
        std::cout << "环入口节点值: " << entry5->val << std::endl;
    } else {
        std::cout << "无环" << std::endl;
    }
    std::cout << std::endl;

    return 0;
}
